package tree.thread_tree;



import java.util.Stack;

public class ThreadTree{
    private tNode root;
    private tNode temp;

    public void setRoot(tNode root) {
        this.root = root;
    }
    /**
     *基于root创建线索二叉树
     */
    public void bulidThreadTree(tNode root){
        tNode pretemp=null;//前置指针,用于保留temp指针的前一个元素
        tNode pre=null;
        Stack<tNode> stack = new Stack<>();
        stack.push(root);

       do{
            tNode temp = stack.pop();
            pre=pretemp;
            if (temp.right!=null)
                stack.push(temp.right);
            else{
                temp.setRightStyle(1);
                if (!stack.empty())
                    temp.right=stack.peek();
                else
                    temp.right=null;
            }
            if (temp.left!=null)
                stack.push(temp.left);
            else{
                temp.setLeftStyle(1);
                temp.left=pretemp;
            }
            pretemp=temp;
        } while(!stack.empty());
    }

    /**
     * 基于线索二叉树的前序遍历
     * @param temp
     */
    public void preTravel(tNode temp){
        if (root==null){
            System.out.println("二叉树为空");
            return;
        }
        System.out.println(temp);
        if (temp.left!=null && temp.getLeftStyle()!=1)
            preTravel(temp.left);
        if (temp.right!=null && temp.getRightStyle()!=1)
            preTravel(temp.right);
    }
}
class tNode{
    private int id;
    private String name;
    public tNode left;
    public tNode right;
    private int leftStyle;//左指针所指节点类型,0为正常孩子节点,1为前驱节点
    private int rightStyle;//右指针所指节点类型,0为正常孩子节点,1为后继节点

    public tNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getLeftStyle() {
        return leftStyle;
    }

    public void setLeftStyle(int leftStyle) {
        this.leftStyle = leftStyle;
    }

    @Override
    public String toString() {
        return "tNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                ", leftStyle=" + leftStyle +
                ", rightStyle=" + rightStyle +
                '}';
    }

    public int getRightStyle() {
        return rightStyle;
    }

    public void setRightStyle(int rightStyle) {
        this.rightStyle = rightStyle;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
}